﻿// 788. 逆序对的数量.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;

/*

https://www.acwing.com/problem/content/790/

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,109]。

输入样例：
6
2 3 4 5 6 1
输出样例：
5
*/

const int N = 100010;
int a[N];
int n; long long  ans;
int tmp[N];


void mergesort(int arr[], int l, int r) {
	if (l >= r) return;
	int mid = l + r >> 1;
	mergesort(arr, l, mid); mergesort(arr, mid + 1, r);

	int i = l; int j = mid + 1; int k = 0;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j]) {
			tmp[k++] = a[i++];
		}
		else {
			ans += mid - i + 1; //当前i 到mid  都比a[j]大  且j在mid+1~ r的范围 构成逆序对
			tmp[k++] = a[j++];
		}
	}
	while (i <= mid) tmp[k++] = a[i++];
	while (j <= r) tmp[k++] = a[j++];

	for (i = l, j = 0; j < k;) a[i++] = tmp[j++];
}



int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	mergesort(a, 0, n - 1);

	cout << ans << endl;

	return 0;
}

 